package sort;

import java.util.ArrayList;

public class MaxKValue {

    public static int maxKValue(Integer[] a,int k){
        if(k<=0||k>a.length){
            return -1;
        }
        int n = a.length;
        int pivot = a[n-1];
        ArrayList<Integer> tmp1 = new ArrayList<Integer>();
        ArrayList<Integer> tmp2 = new ArrayList<Integer>();
        //ArrayList<Integer> tmp3 = new ArrayList<>();
        int i = 0;
        while(i<n){
           int currentValue = a[i++];
            if(currentValue>pivot){
                tmp1.add(currentValue);
            }else if(currentValue<pivot){
                tmp2.add(currentValue);
            }
        }
        //if(tmp1.size()==0)
//        tmp3.addAll(tmp1);
//        tmp3.add(pivot);
//        tmp3.addAll(tmp2);
        int p = tmp1.size();
        if(p+1==k){
            return pivot;
        }else if(p+1<k){
            Integer[] array = tmp2.toArray(new Integer[]{});
            return maxKValue(array,k-p-1);
        }else if(p+1>k){
            Integer[] array = tmp1.toArray(new Integer[]{});
            return maxKValue(array,k);
        }
        return -1;
    }

    public static void main(String[] args){
        Integer[] a = {6,1,3,5,7,2,4,9,11,8};
        int value = maxKValue(a,4);
        System.out.printf("----("+value+")-----");
    }
}
